package algorithm.MonotonePriorityStack.leetcode_1504;

import java.util.Stack;

class Solution {
    public int numSubmat(int[][] mat) {
        int[] heights = new int[mat[0].length];
        int ans = 0;

        int n = mat.length;
        int m = mat[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                heights[j] = mat[i][j] == 1 ? heights[j] + 1 : 0;
            }
            Stack<Integer> stack = new Stack<>();
            int[] f = new int[m];
            for (int j = 0; j < m; j++) {
                int height = heights[j];
                while (!stack.isEmpty() && height < heights[stack.peek()]) {
                    stack.pop();
                }
                int left = stack.isEmpty() ? -1 : stack.peek();
                if (left ==-1){
                    f[ j] =height*(j+1);
                }
                else{
                    f[j] = height*(j-left)+f[left];
                }
                ans += f[j];
                stack.push(j);
            }
        }
        return ans ;
    }
}